#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
typedef struct DLinkNode {
	DataType data;
	struct DLinkNode* prev;
	struct DLinkNode* next;
}DNode;
void CreateListFront(DNode* &L,DataType arr[],int n)
{
	DNode* s;
	L = (DNode*)malloc(sizeof(DNode));
	L->next = L->prev = NULL;
	for (int i=0;i<n;i++)
	{
		s = (DNode*)malloc(sizeof(DNode));
		s->data = arr[i];
		s->next = L->next;
		if (L->next)
			L->next->prev = s;
		L->next = s;
		s->prev = L;
	}
}
void CreateListFront(DNode* &L,DataType arr[],int n)
{
	DNode* s;
	L = (DNode*)malloc(sizeof(DNode));
	L->next = L->prev = NULL;
	for (int i=0;i<n;i++)
	{
		s = (DNode*)malloc(sizeof(DNode));
		s->data = arr[i];
		s->next = L->next;
		if (L->next)
			L->next->prev = s;
		L->next = s;
		s->prev = L;
	}
}
void CreateList(DNode*& L, DataType arr[], int n)
{
	DNode* s, * r;
	L = (DNode*)malloc(sizeof(DNode));
	L->next = L->prev = NULL;
	L = r;
	for (int i=0;i<n;i++)
	{
		s = (DNode*)malloc(sizeof(DNode));
		s->data = arr[i];
		r->next = s;
		s->prev = r;
		r = s;
	}
	r->next = NULL;
}
void InitList(DNode* &L)
{
	L = (DNode*)malloc(sizeof(DNode));
	L->next = L->prev = NULL;
}
void InitList(DNode* &L)
{
	L = (DNode*)malloc(sizeof(DNode));
	L->next = L->prev = NULL;
}
void DestroyList(DNode* &L)
{
	DNode* prev = L, * p = prev->next;
	while (p)
	{
		free(prev);
		prev = p;
		p = p->next;
	}
	free(prev);
}
bool EmptyList(DNode* L)
{
	return (L->next == L->prev == NULL);
}
bool ListLength(DNode* &L)
{
	int count = 0;
	DNode* p = L;
	while (p)
	{
		count++;
		p = p->next;
	}
	return count;
}
void DispList(DNode* &L)
{
	DNode* p = L;
	while (p)
	{
		printf("%c ", p->data);
		p = p->next;
	}
	printf("\n");
}
bool GetElem(DNode* &L,int i,DataType &e)
{
	int j = 0;
	DNode* p = L;
	if (i < 1)
		return false;
	while (j<i && p)
	{
		j++;
		p = p->next;
	}
	if (!p)
		return false;
	else
	{
		e = p->data;
		return true;
	}
}
bool GetElem(DNode* &L,int i,DataType &e)
{
	DNode* p = L;
	int j = 0;
	if (i < 1)
		return false;
	while (j < i && p)
	{
		j++;
		p = p->next;
	}
	if (!p)
		return false;
	else
	{
		e = p->data;
		return true;
	}
}
int LocateElem(DNode* L,DataType e)
{
	DNode* p = L->next;
	int i = 0;
	while (p && p->data != e)
	{
		p = p->next;
		i++;
	}
	if (!p)
		return 0;
	else
		return i;
}
int LocateElem(DNode* L, DataType e)
{
	int i = 1;
	DNode* p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
		i++;
	}
	if (!p)
		return 0;
	else
		return i;
}
bool InsertElem(DNode* &L,int i,DataType e)
{
	int j = 0;
	DNode* p = L, * s;
	if (i < 1)
		return false;
	while (j < i - 1 && p)
	{
		j++;
		p = p->next;
	}
	if (!p)
		return false;
	else
	{
		s = (DNode*)malloc(sizeof(DNode));
		s->data = e;
		s->next = p->next;
		if (p->next)
			p->next->prev = s;
		p->next = s;
		return true;
	}
}
bool InsertList(DNode* &L,int i,DataType e)
{
	DNode* p = L->next, * s;
	int i = 0;
	if (i < 1)
		return false;
	while (j < i - 1 && p)
	{
		p = p->next;
		j++;
	}
	if (!p)
		return false;
	else
	{
		s = (DNode*)malloc(sizeof(DNode));
		s->data = e;
		s->next = p->next;
		if (p->next)
			p->next->prev = s;
		p->next = s;
		s->prev = p;
		return true;
	}
}bool ListDelete(DNode* &L,int i,DataType &e)
{
	int j = 0;
	DNode* p = L, * q;
	if (i < 1)
		return false;
	while (j < i - 1 && p)
	{
		j++;
		p = p->next;
	}
	if (!p)
		return false;
	else
	{
		q = p->next;
		if (!q)
			return false;
		e = q->data;
		p->next = q->next;
		if (p->next)
			q->next->prev = p;
		free(q);
		return true;
	}
}
bool ListDelete(DNode* &L,int i,DataType &e)
{
	int j = 0;
	DNode* p = L, * q;
	if (i < 1)
		return false;
	while (j < i - 1 && p)
	{
		j++;
		p = p->next;
	}
	if (!p)
		return false;
	else
	{
		q = p->next;
		if (!q)
			return false;
		p->next = q->next;
		if (q->next)
			q->next->prev = p;
		free(q);
		return true;
	}
}